package leetcode.tencent;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
 * 每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）
 * 1.第一个整数是 0
 * 2.一个整数在序列中出现 不超过一次
 * 3.每对 相邻 整数的二进制表示 恰好一位不同 ，且第一个 和 最后一个 整数的二进制表示 恰好一位不同
 * 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。(1 <= n <= 16)
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gray-code
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/20 13:39
 */
public class grayCode {

    public static void main(String[] args) {
        grayCode(2);
    }

    // 输入：n = 2
    // 输出：[0,1,3,2]
    // [00,01,11,10]
    // n = 3
    // 000 001 010 011 100 101 110 111
    //
    // 000 001 011 111 101 100 110 010
    // 思路：二级制表示恰好一位不同，整数范围 是 [0, 2^n - 1], 也就是每个数字必须出现且仅出现一次
    // 第一个整数必须是 0，
    // 格雷码  利用 i >> 1 ^ i
    static public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            res.add(i >> 1 ^ i);
        }
        return res;
    }
}
